package chapter05

import scala.annotation.tailrec

object Test10_Recursion {

  def main(args: Array[String]): Unit = {
    // 递归，阶乘
    println(fact(5))
  }

  def fact(n:Int):Int={
    if(n==0) return 1
    fact(n-1)*n
  }

  // 尾递归

  /**
   * 递归的不正确使用会造成栈溢出，其本质在于
   * 上个调用方法栈没有被释放，持续调用下一个
   * 方法的上下文一直压入。直到虚拟机栈的空间消耗殆尽
   *
   * 那么在函数变成语言中，有对递归进行优化，scala也一样
   * 如果你的每次递归结果都需要根据下一次的递归结果来计算的话
   * 也就是需要下一个完全执行完毕且返回才能确定结果。
   * 我们可以使用尾递归。
   *
   * 在这个方法中，我们会将所有的结果存储到result中
   * 通过传递这个result，将结果不断累加到这个变量中，这样的话
   * 就可以放心的释放掉上一个方法栈了，相当于直接覆盖了上一个。
   * 从始至终都只有一个在执行，极大优化了递归
   * @param n
   * @return
   */
  def tailFact(n:Int):Int = {
    // 这个注解，可以保证你这个一定是个尾递归
    @tailrec
    def loop(n:Int,result:Int):Int={
      if(n==0) return result
      // 将result传递下去
      loop(n-1,result*n)
    }
    loop(n,1)
  }


}
